/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 二分查找 + 位运算：time: O((logn)平方), space: O(1)
// 1. dfs：持续找左子树直到叶子节点，求二叉树深度h；
// 2. 二分查找：二分法结合位运算求最后一层节点数，根据完全二叉树可得到总节点数
func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}

	// calulate h, from 0
	h := 0
	for node := root; node.Left != nil; node = node.Left {
		h++
	}

	// while full binary tree is h, total count will <= 2^(h+1) - 1
	return sort.Search(1<<(h+1), func(k int) bool {
		if k <= 1<<h {
			return false
		}

		bits := 1 << (h - 1)
		node := root
		for node != nil && bits > 0 {
			if bits&k == 0 {
				// if 0, turn to left child
				node = node.Left
			} else {
				node = node.Right
			}
			bits >>= 1
		}
		// node == nil, at the time, will calculate one more node
		return node == nil
	}) - 1
}